A plurality of methods have been proposed for locating moving object, such as the Global Positioning System (GPS) which can locate object with high location precision (A GPS satellite constellation transmits to the ground such two kinds of spread spectrum codes as C/A code and P code. The C/A code is for civil usage, and its locating precision is about 100 meters and can be enhanced to 10 meters when using the difference code technology. The P code with higher precision is for military code, its locating precision is less than 10 meters and its velocity precision provided is 0.06–0.1 m/s). In addition, the current cell phones can be located by a base station, but the locating precision is relatively low (The locating precision depends on the radius of the located cell. For example, in the urban area of Beijing, the density of base stations is relatively high and the location precision can reach about 200 meters with technology of cell of origin, while in the rural area the density of base stations is relatively low and the locating precision can only reach one or two kilometers).
At present, the existing systems utilize these locating technologies to continuously locate moving objects and store the obtained location data in a database, thereby many kinds of queries can be executed based on the location data of moving objects in the database. We refer to the whole system as a moving object database (MOD). Therefore, as shown in FIG. 1, the hardware of the moving object database system comprises: a mobile unit, a locating device, a communication interface and a server where the database is located. The mobile unit is a device which is installed on a moving object and can be monitored, such as a mobile phone, a GPS receiver, etc. When a GPS receiver is used, both the locating device and the mobile unit together are often called a mobile unit. They send the location data of moving objects into the database via the communication interface and the database offers an external query and other service interfaces.
The following are some examples of database query applications: While a person is entering the range of 500 meters near McDonald, an E-coupon is sent to his/her mobile phone by the service provider; and a taxi company manager can query the locations of the taxies belonging to his company from 9:00 AM yesterday to 2:00 PM today, etc. The MOD can be used in taxi management, logistics, location-based service, etc.
In such a system, if a discrete point model for storage is used in database, i.e., the location data at a discrete time point are recorded by the database, in order to record the locations of the discrete time points of moving objects, large number of locations of moving objects should be tracked in real time, in other words, the frequency for tracking moving objects is very high, then a lot of location data of moving objects will be inserted to the database in a unit time. On one hand the database can not stand such a high inserting rate, and on the other hand a lot of storage space is needed. Let us take a moving object database system of taxi management as an example here to give further explain: suppose there are 30,000 taxis in total in a taxi company, each taxi is located per minute and its location data is sent to a database, then 500 inserting operation will be executed by the database in one second. The database can not sustain such high rate data insertion operations, and such a moving object database system can not work normally.
Another problem is for the storage space. The location query at non-sampled time points generally uses technologies such as linear interpolation or fitting. Taking linear interpolation as an example, the object location X at the time of T (T1≦T≦T2) is the linear interpolation between the object location X1 at the time of T1 and the object location X2 at the time of T2, as shown in the following formula.                     X        =                              X            1                    +                                                                      X                  2                                -                                  X                  1                                                                              T                  2                                -                                  T                  1                                                      ·                          (                              T                -                                  T                  1                                            )                                                          (        1        )            
FIG. 2 shows the error of location query, which is the distance between the interpolated location and the actual location of the point.
Thinking the locations stored in the database are 2-Dimension data for recording the locations of the taxies of the taxi company and each location needs 16 bytes, then the service providers for the taxi company have to store 659.1M data a day, 19.3G data a month, and nearly 235G data a year. Still only the situation of pure data storage except the aspect of database management, such as indexing, is considered. The great data storage capacity is also difficult for database management, and the expense for storage space can not be negligible.
If we can compress such data and saved the compressed data in the database, then the above problems can be solved effectively. The compression can be considered in the following several aspects:                (1) Taking the redundancy-removing filtering method used in U.S. Pat. No. 6,327,533 B1 as an example, a time or displacement threshold is set, and if the time or displacement of an object does not exceed the threshold, then the location of the moving object will not be recorded, thereby achieving the compression. What is recorded in the database is still the location of the moving object, and the query process is very convenient. But when a lot of moving objects are moving concurrently, the method is ineffective, there are still a lot of insertion operations in the database and the system is possibly incapable of operating normally.        (2) Constant speed translational movement is a kind of very important movement for moving objects. In U.S. Pat. No. 5,187,689, it is also mentioned that translational motion can be translationally predicted, using this kind of linear prediction method can also reduce storage space, and what is recorded in the database is still the locations of the object, which is very convenient for query process. But when a lot of moving objects are moving randomly nearby, the compression ratio is very low, there are still a lot of insertion operations in the database, and the system is also possibly incapable of operating normally.        (3) The motion traces of the object can be treated as data curve. By performing data regression or transformation on these curves and storing the regression coefficients or the transformation coefficients in the database, the compression can also be achieved. But this method has two disadvantages as follows: (a) the relationship between the errors of the fitted or transformed curve, and the original curve, and the mathematical format of the curve is usually very complicated and difficult to be obtained, while using a curve fitting in a fixed manner is difficult to ensure the precision when performing a query on locations; (b) a complicated inverse transformation should be conducted when querying locations, which greatly influences the speed of query process. Many query operations of the database can not carried out directly.        